Depth First Search(DFS)- Data Structure Algorithm

Graph and Trees are two similar like Data structures with some difference, and Depth First Search is a traversing or searching algorithm that can apply to both the structures. The DFS algorithm was investigated by Charles Pierre Trémaux back in the 19 ^th century. Here in this article, we have covered the DFS (Depth First Search) algorithm for Graph Data Structures.

What is DFS?

DFS Stands for Depth First Search and it is an algorithm used to traverse through a Graph data structure and can also be used for searching purpose. As we know that in a Graph Data Structure, we use edges and vertices so to traverse from one vertex to another we use edges, in DFS we visit each vertex only one time, once we have visited a vertex (node) so we block all the edges pointing to it, so we do not visit the same node twice. If we use the DFS algorithm to traverse through all nodes, here our main goal to search as deeply as possible. We use the stack data structure along with DFS, which is used to hold all the visited node. The DFS algorithm traversing for searching start from the head of the node and end with the last visited leaf node. In between if the algorithm leads to one of the leaf nodes, then it backtracks from that leaf node to the most recent node and tries to visit the unvisited node. In DFS we often use the recursion for backtracking.

DFS Algorithm

Step1: Start Traversing with the head node.
Step 2: Visit the adjacent node and push it into the stack.
Step 3: Repeat Step 2 until reach the leaf node.
Step 4: Once reached to the leaf node pop it from the stack.
Step 5: Pop all the nodes that have been push into the stack and have no further adjacent node to visit (backtracking).

DFS Properties

Space and time complexity of DFS vary according to its application
The conventional use of DFS to traverse through a given graph.
The Space complexity of DFS depends upon the number of vertices.
DFS has many real-world applications and heavily used in Artificial Intelligence.

Advantages and Disadvantages of DFS

Advantages

Use less memory.
It can find the largest distance with less time because it tries to find all the leaf nodes first.

Disadvantage

Does not provides an optimal solution
Also, visit the unwanted path.

DFS Applications

Topological sorting
Finding the bridge of a graph
Generating words to plot set of groups.
Finding bi-connectivity in the graph.

DFS Implementation

Python

from collections import defaultdict 
class Graph: 
  def __init__(self): 
    self.graph = defaultdict(list) 
  def addEdge(self,u,v): 
    self.graph[u].append(v) 
  def DFSUtil(self, v, visited): 
    visited[v]= True
    print(v) 
    for i in self.graph[v]: 
      if visited[i] == False: 
        self.DFSUtil(i, visited) 
  def DFS(self): 
    V = len(self.graph) #total vertices 
    visited =[False]*(V) 
    for i in range(V): 
      if visited[i] == False: 
        self.DFSUtil(i, visited) 
g = Graph() # Create a graph
g.addEdge(0, 1) 
g.addEdge(0, 2) 
g.addEdge(1, 2) 
g.addEdge(2, 0) 
g.addEdge(2, 3) 
g.addEdge(3, 3) 
print("Following is Depth First Traversal")
g.DFS()

OUTPUT:

Following is Depth First Traversal
0
1
2
3

People are also reading:

Depth First Search(DFS)- DSA

Table of Content